<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /* 
    二叉搜索树中的算法
    二分搜索算法用于针对已排序的集合进行搜索。
    */

    var Arr = [5, 7, 4, 2, 9];


    // 这里使用插入排序 并不好  插入排序是最慢的方法  一般用快速排序配合二分搜索
    function insertSort (array) {
      const { length } = array;
      let temp;
      for (let i = 1; i < length; i++) {
        temp = array[i];
        let j = i;
        while (j > 0 && array[j - 1] > temp) {
          array[j] = array[j - 1];
          j--;
        }
        array[j] = temp;
      }
      return array
    }

    function binarySearch (find, arr, start, end) {
      // 处理第一次 未传入start end的情况
      start = start || 0
      end = end || arr.length - 1

      // 先将数组排序
      arr = insertSort(arr)

      if (start <= end && find >= arr[start] && find <= arr[end] ) {
        // 处理满足条件的情况
        if (find === arr[start]) {
          return start
        }
        if (find === arr[end]) {
          return end
        }

        // 取中间值  这里做一个向上取整的逻辑
        const mid = Math.ceil((start + end) / 2)

        if (find === arr[mid]) {
          return mid
        } else if (find > arr[mid]) {
          return binarySearch(find, arr, mid + 1, end)
        } else {
          return binarySearch(find, arr, start, mid - 1)
        }
      }

      return -1

    }
    binarySearch(9, Arr)



  </script>
</body>

</html>